import collections
from typing import List


class Solution:
    def minJumps(self, arr: List[int]) -> int:
        index = collections.defaultdict(list)
        for i, num in enumerate(arr):
            index[num].append(i)

        visited_num = set()
        visited_idx = {0}
        queue = collections.deque([0])

        step = 0
        while queue:
            for _ in range(len(queue)):
                i1 = queue.popleft()
                if i1 == len(arr) - 1:
                    return step
                if i1 - 1 >= 0 and i1 - 1 not in visited_idx:
                    queue.append(i1 - 1)
                    visited_idx.add(i1 - 1)
                if i1 + 1 < len(arr) and i1 + 1 not in visited_idx:
                    queue.append(i1 + 1)
                    visited_idx.add(i1 + 1)
                if arr[i1] not in visited_num:
                    visited_num.add(arr[i1])
                    for i2 in index[arr[i1]]:
                        if i2 not in visited_idx:
                            queue.append(i2)
                            visited_idx.add(i2)
            step += 1


if __name__ == "__main__":
    print(Solution().minJumps(arr=[100, -23, -23, 404, 100, 23, 23, 23, 3, 404]))  # 3
    print(Solution().minJumps(arr=[7]))  # 0
    print(Solution().minJumps(arr=[7, 6, 9, 6, 9, 6, 9, 7]))  # 1
    print(Solution().minJumps(arr=[6, 1, 9]))  # 2
    print(Solution().minJumps(arr=[11, 22, 7, 7, 7, 7, 7, 7, 7, 22, 13]))  # 3
